package com.company.ljh.sort;

import java.util.Random;

public class 堆排序 {

    public static void main(String[] args) {
        堆排序 d = new 堆排序();
        d.maxScore(new int[]{4,2,3,1,1},new int[]{7,5,10,9,6},1);
    }
    private static Random random = new Random(System.currentTimeMillis());

    public long maxScore(int[] nums1, int[] nums2, int k) {
        int result = 0;
        //先对num2进行排序
        partition(nums2,nums1,0,nums1.length-1);
        int minHeap[] = new int[nums1.length];
        for(int i = 0;i < nums2.length ;i++){
            //从第0大值开始建立小根堆
            if(i <= k -1){
                add(minHeap,nums1[i],i,k);
            }else{
                int sum = add(minHeap,nums1[i],k,k);
                int data = sum * nums2[i];
                result = result>data?result:data;
            }

        }
        return result;
    }
    //堆添加元素做上浮操作，先将元素放到最后位置，在大于父亲元素则交换，一直递归到小于父亲为止
    public int add(int nums[],int num,int heapSize,int maxSize){

        //当前值比最小值还小，不入
        if(num < nums[0]){

        }else{
            nums[heapSize++] =  num;
            //调整
            adjust(nums,heapSize/2 -1,heapSize);
        }
        if(heapSize > maxSize){
            pop(nums,heapSize);
        }
        int sum= 0;
        for(int i = 0;i<maxSize;i++){
            sum+=nums[i];
        }

        return sum;
    }
    //将最后一个元素交换到头节点，弹出第一个元素，再重新调整堆
    public int pop(int [] nums,int heapSize){
        int num = nums[0];
        nums[0] = nums[heapSize -1];
        adjust(nums,0,--heapSize);
        return num;
    }
    public void buildMinHeap(int []nums,int heapSize){
        //循环调整每一个非叶子节点
        for(int i = (heapSize/2 -1);i >=0;i--){
            adjust(nums,i,heapSize);
        }

    }
    //从下向上调整
    public void adjust(int []nums,int i,int heapSize){
        if(heapSize == 1){
            return ;
        }
        //左子节点
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int min = i;
        //选择最大的结点替换到头节点
        if(left < heapSize && nums[left] < nums[min]){
            min = left;
        }
        if(right < heapSize && nums[right] < nums[min]){
            min = right;
        }
        if(min != i){
            swap(nums,left,i);
            //递归子节点
            adjust(nums,left,heapSize);
        }
    }
    public void swap(int nums[],int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
    //快排
    private  void partition(int[]nums,int[] nums2,int start,int end){

        //随机选取一个数当作比较数
        int pivot = start + random.nextInt(end - start +1);
        //将pivot放置到第一位，方便交换
        sortSwap(nums,nums2,start,pivot);
        //同时将pivot指向最开始
        pivot = start;
        //从第二位开始遍历
        int index = start+1;
        int right = end;
        //左右指针，指向当前交换的数
        while(pivot < right){
            if(nums[index] >= nums[pivot]){
                //小于等于当前数，放左边
                sortSwap(nums,nums2,index++,pivot++);
            }else{
                //放右边,右指针前移一位，当前指针不变
                sortSwap(nums,nums2,index,right--);
            }
        }

        if(start < pivot-1){
            //两边元素分别递归
            partition(nums,nums2,start,pivot-1);
        }
        if(pivot+1 <end) {
            partition(nums,nums2, pivot + 1, end);
        }

    }
    //连带排序
    private  void sortSwap(int [] nums,int[]nums2,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
        int temp2 = nums2[index1];
        nums2[index1] = nums2[index2];
        nums2[index2] = temp2;
    }


}
